In a system with a storage hierarchy, selected blocks of data from main storage are stored in a local buffer or cache memory for fast access by the processing units or processors. When the processor requests new data, the system first checks the cache memory to determine whether it is available. If the data is available in the cache memory, the data is provided to the processor. In the event the data is not available in the cache memory, the data is retrieved from the main memory, which is on a lower level in the storage hierarchy.
To supply some modern processors with instructions and data for this operation, cache memories are sometimes used which are capable of extremely rapid information retrieval and transmission. Such cache memories are available, usually in the form of Random Access Memories (RAM). Such fast memories, however, are generally on the order of a few thousand bytes. Since only a very few blocks of data can be stored in memories of that size, the main memory is of a larger byte size, but with slower access and retrieval time. The lower level main memory includes larger RAMs with slower retrieval speeds, bubble memories, disc memories of various types and other memories.
Two principles insure that use of a cache memory will be successful. The first principle is spatial locality. When a given program is run, the instructions the program uses and the related data tend to be stored in close proximity with one another. Thus, a relatively small block of instructions and data can perform a large portion of the program. The second principle is temporal locality which states that once a given instruction or set of instructions is accessed, it is likely that it will be accessed again in the near future. Again, this tends to make the accessibility of a small group of instructions and data extremely useful.
A commonly used method to optimize computer operations is to couple a cache memory directly to the central processing unit (CPU) and to couple other larger memories to both the cache memory and the CPU as lower level memories. In this manner, the cache memory can supply the CPU with the data needed at a rate which will allow fast CPU operation. Lower level memories fill data into the cache memory, thereby keeping it full. If a required block of data is not in the cache memory when the CPU requires it, the data block can be obtained from lower level memory. In other words, if a miss to cache memory occurs, the data is obtained from the lower level memory.
A cache memory can be accessed in at least two ways. The first, physical addressing, is when data in the cache memory is accessed using a physical address which specifies the actual location of the data. The second way is virtual addressing in which the data in the cache memory is referenced through a virtual address. In order to retrieve data from a physically addressed cache memory, the virtual addresses must be translated to the physical addresses using a structure called a virtual to physical translation buffer. Both physically and virtually addressed cache memories are in current use in computer design.
The use of virtual addresses for data access from a cache imposes requirements that are not found in physically addressed cache memories. For example, a physical address to virtual cache index translation mechanism (backmap) must be provided. The backmap is used by the physically addressed portion of the system to locate data which is stored in the virtually addressed cache.
Caches work most efficiently when they are as full with data as possible. This is because fewer attempts to find the data in the cache memory will result in misses which require retrieval from the lower level memories. Therefore, it is desirable to minimize flushing of the cache memory to the smallest number of data blocks possible. Refilling of the cache with new data should be done quickly and efficiently.
When data in the cache memory is modified by other devices such as other processors, the data within the cache memory must be invalidated since it is no longer current. Accordingly, a data block in the virtually addressed cache is typically invalidated when it contains the data that is being modified by the devices in the system. Subsequently, when data is filled into the cache memory, a corresponding entry must be provided in the backmap.
Another problem with the use of virtual addressing is the presence of synonyms in the cache memory. Synonyms are data entries with the same physical address but with different virtual addresses. The presence of synonyms disrupts efficient retrieval of data from cache memory. The process of detecting synonyms may be time-consuming and require complicated logic.